package leetcode.programmer;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

// 面试题 01.04. 回文排列
public class CanPermutePalindrome {
    public static void main(String[] args) {
        System.out.println(canPermutePalindrome("aa"));
    }

    // 判断单个字母只有一个
    public static boolean canPermutePalindrome(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.putIfAbsent(c, 0);
            map.put(c, map.get(c) + 1);
        }
        int count = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                count++;
            }
        }
        return count == 1 || count == 0;
    }

    // set
    public static boolean canPermutePalindrome2(String s) {
        HashSet<Character> set = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (set.contains(c)) {
                set.remove(c);
            } else {
                set.add(c);
            }
        }
        return set.size() == 1 || set.size() == 0;
    }

    // 数组版统计
    public static boolean canPermutePalindrome3(String s) {
        int[] cnt = new int[128]; // 一般都给128的长度
        for (char c : s.toCharArray()) {
            cnt[c]++;
        }
        int count = 0;
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] % 2 != 0) {
                count++;
            }
        }
        return count <= 1;
    }

    // 数组版统计 优化
    public static boolean canPermutePalindrome31(String s) {
        int[] cnt = new int[128]; // 一般都给128的长度
        boolean flag = false;
        for (char c : s.toCharArray()) {
            cnt[c]++;
        }

        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] % 2 != 0 && !flag) {
                flag = true;
            } else if (cnt[i] % 2 != 0) {
                return false;
            }
        }
        return true;
    }
}
